package com.chj.leetcode.tijie850to900;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code862_ShortestSubarrayWithSumAtLeastK {
	public static int shortestSubarray(int[] arr, int K) {
		// if (arr == null || w < 1 || arr.length < w) {
		// return null;
		// }
		// 下标 值 大 -> 小
		Deque<Integer> qmax = new ArrayDeque<Integer>();
		// int[] res = new int[arr.length - w + 1];
		int index = 0;
		int left = 0;
		int preSum = 0;
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) { // 窗口（刚才讲的）的R
			preSum += arr[i];
			int tmp = preSum;
			// i -> arr[i]
			// while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
			while (!qmax.isEmpty() && preSum >= K) {
				// qmax.pollLast();
				left = qmax.pollFirst();
				preSum -= arr[left];
			}
			qmax.addLast(i);
			index = left;
			while (index <= i) {
				if (tmp >= K) {
					ans = Math.min(ans, i - index + 1);
				}
				tmp -= arr[index];
				index++;
			}
			// if (qmax.peekFirst() == i - w) { // i - w 过期的下标
//			while (tmp >= K && index <= left) {
//				ans = Math.min(ans, i - index + 1);
//				index++;
//			}
			// if (i >= w - 1) { // 窗口形成了
			// res[index++] = arr[qmax.peekFirst()];
			// }
		}

//		while (index < arr.length) {
//			if (preSum >= K) {
//				ans = Math.min(ans, arr.length - index);
//			}
//			preSum -= arr[index];
//			index++;
//		}

		if (ans == Integer.MAX_VALUE) {
			ans = -1;
		}
		return ans;
	}

	public static int maxLengthAwesome(int[] arr, int k) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
//		System.out.println("arr: ");
//		printArray(arr);
		int[] minSums = new int[arr.length];
		int[] minSumEnds = new int[arr.length];
		minSums[arr.length - 1] = arr[arr.length - 1];
		minSumEnds[arr.length - 1] = arr.length - 1;
		for (int i = arr.length - 2; i >= 0; i--) {
			if (minSums[i + 1] < 0) {
				minSums[i] = arr[i] + minSums[i + 1];
				minSumEnds[i] = minSumEnds[i + 1];
			} else {
				minSums[i] = arr[i];
				minSumEnds[i] = i;
			}
		}

//		System.out.println("minSums: ");
//		printArray(minSums);
//		System.out.println("minSumEnds: ");
//		printArray(minSumEnds);

		int end = 0;
		int sum = 0;
		int res = 10000000;
		// i是窗口的最左的位置，end是窗口最右位置的下一个位置
		for (int i = 0; i < arr.length; i++) {
			// while循环结束之后：
			// 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
			// 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
			while (end < arr.length && sum + minSums[end] >= k) {
				sum += minSums[end];
				end = minSumEnds[end] + 1;
			}
			res = Math.min(res, end - i);
			if (end > i) { // 窗口内还有数
				sum -= arr[i];
			} else { // 窗口内已经没有数了，说明从i开头的所有子数组累加和都不可能<=k
				end = i + 1;
			}
		}
		return res;
	}

	public static int shortestSubarray02(int[] A, int k) {
		int n = A.length;
		int res = Integer.MAX_VALUE;
		int[] preSum = new int[n + 1];
		// 前缀和, preSum[j] - preSum[i] = sum from i to j - 1;
		// distance: (j - 1) - i + 1 = j - i;
		for (int i = 0; i < n; i++) {
			preSum[i + 1] = preSum[i] + A[i];
		}
		// 现在需求: 求preSum数组中j > i && preSum[j] - preSum[i] >= k
		// 单调递增双端队列
		Deque<Integer> deq = new ArrayDeque<>();
		int len = preSum.length;
		for (int i = 0; i < len; i++) {
			// 单调递增的, 比当前数大的相减肯定为负数, 并不满足大于等k
			while (!deq.isEmpty() && preSum[i] <= preSum[deq.getLast()]) {
				deq.pollLast();
			}
			// 队列中剩余的相减都会大于0
			// 从前往后找, 为什么弹出?
			// 因为对当前数来说, 如果这些数是满足要求的, 后面再来的数哪怕也满足要求
			// 距离也会更远
			while (!deq.isEmpty() && preSum[i] - preSum[deq.getFirst()] >= k) {
				res = Math.min(res, i - deq.getFirst());
				deq.pollFirst();
			}
			deq.addLast(i);
		}
		// 没有符合条件的
		return res == Integer.MAX_VALUE ? -1 : res;
	}

//作者：zhuobo
//链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/guan-fang-ti-jie-xiang-jie-dan-diao-shua-oh9y/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static int shortestSubarray03(int[] A, int k) {
		int n = A.length;
		int res = Integer.MAX_VALUE;
		int[] preSum = new int[n + 1];
		// 前缀和, preSum[j] - preSum[i] = sum from i to j - 1;
		// distance: (j - 1) - i + 1 = j - i;
		for (int i = 0; i < n; i++) {
			preSum[i + 1] = preSum[i] + A[i];
		}
		// 现在需求: 求preSum数组中j > i && preSum[j] - preSum[i] >= k
		// 单调递增双端队列
		Deque<Integer> deq = new ArrayDeque<>();
		int len = preSum.length;
		for (int i = 0; i < len; i++) {
			// 单调递增的, 比当前数大的相减肯定为负数, 并不满足大于等k
			while (!deq.isEmpty() && preSum[i] <= preSum[deq.getLast()]) {
				deq.pollLast();
			}
			// 队列中剩余的相减都会大于0
			// 从前往后找, 为什么弹出?
			// 因为对当前数来说, 如果这些数是满足要求的, 后面再来的数哪怕也满足要求
			// 距离也会更远
//			while (!deq.isEmpty() && preSum[i] - preSum[deq.getFirst()] >= k) {
//				res = Math.min(res, i - deq.getFirst());
//				deq.pollFirst();
//			}
			deq.addLast(i);

			while (preSum[i] - preSum[deq.getFirst()] >= k) {
				res = Math.min(res, i - deq.getFirst());
				deq.pollFirst();
			}
		}
		// 没有符合条件的
		return res == Integer.MAX_VALUE ? -1 : res;
	}

	public static void main(String[] args) {
		{
			int[] arr = { 84, -37, 32, 40, 95 };
			int k = 167;
			System.out.println(shortestSubarray03(arr, k));
		}

		{
			int[] arr = { 84, -37, 32, 40, 95 };
			int k = 167;
			System.out.println(maxLengthAwesome(arr, k));
		}
	}
}
